package com.yeban.base.day04;

/**
 * @Desc TODO
 * @Author yeban
 * @Date 2025/9/28
 */
// 折半查找
// 需求2：有一个数列：8,4,2,1,23,344,12，此时从键盘中任意输入一个数据，判断数列中是否包含此数
// 解法：先冒泡排序，再折半查找是否包含
public class SortTest02 {

    public static void main(String[] args) {

        int[] arr = { 8, 4, 2, 1, 23, 344, 12 };

        // 查找的数字
        int key = 23;

        int len = arr.length;
        // 冒泡排序
        for (int i = 0; i < len - 1; i++) {
            for (int j = 0; j < len - i - 1; j++) {
                if(arr[j] > arr[j+1]){
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }

        int left = 0;
        int right = len - 1;

        // 折半查找
        // 循环结束条件 right > left
        while(left <= right){
            int middle = (left + right) >> 1;
            // 落在左半边
            if(key < arr[middle]) {
                right = middle - 1;
            }

            // 落在右半边
            else if(key > arr[middle]) {
                left = middle + 1;
            }

            //数字命中了
            else {
                System.out.println("所需要查找的数字为：" + arr[middle]);
                break;
            }

            if (left > right) {
                System.out.println("你所要查找的数字不存在");
            }

        }

    }
}
